# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

head=ListNode(4)
head.next=ListNode(2)
head.next.next=ListNode(1)
head.next.next.next=ListNode(3)
def insertionSortList(head: ListNode) -> ListNode:
    NullPointHead=ListNode()
    pointerProcess=head
    while pointerProcess:
        nextPro = pointerProcess.next
        #外层循环表示待插入的元素
        pre=NullPointHead
        while pre:
            if pre.next==None:
                #表示当前的排队的队列为空或者说是已经到了列表的尾部
                pre.next=pointerProcess
                pointerProcess.next=None
                break
            if pre.next.val>=pointerProcess.val:
                #找到待插入位置了
                pointerProcess.next=pre.next
                pre.next=pointerProcess
                #退出循环
                break
            pre=pre.next
        pointerProcess=nextPro

    while NullPointHead:
        print(NullPointHead.val)
        NullPointHead=NullPointHead.next
insertionSortList(head)